package 牛客.链表;

import java.util.Scanner;

class Node{
    Object data;
    Node prev;
    Node next;

    public Node(Object data, Node prev, Node next) {
        this.data = data;
        this.prev = prev;
        this.next = next;
    }
}
public class DoubleLink{
    Node end;
    Node head;
    int size;

    //初始化
    public void Initiate(){
        end = new Node(null, null, null);
        head = new Node(null, null, end);
        end.prev = head;
        end.next = head;
        size = 0;
    }

    //获取链表长度
    public int Length(){
        return size;
    }
    //取第i个位置的元素
    public Node getNode(int i){
        Node p;
        if(i <= size){
            if(i >= size/2){
                p = end;
                for (int j = Length(); j > i ; j--)
                    p = p.prev;
            }
            else{
                p = head;
                for (int j = 0; j <= i; j++)
                    p = p.next;
            }
            return p;
        }
        else{
            System.out.println("i索引不合法！");
            return null;
        }
    }

    //在位置i插入元素
    public void Insert(int i, Object obj){
        Node p = getNode(i);
        if(p != null) {
            Node q = new Node(obj, p.prev, p);
            p.prev.next = q;
            p.prev = q;
            size++;
        }
    }

    //删除位置i的元素
    public void Delete(int i){
        Node p  = getNode(i);
        if(p != null) {
            p.prev.next = p.next;
            p.next.prev = p.prev;
            System.out.println("删除" + p.data + "成功！");
            size--;
        }
    }

    //判断链表是否有环
    public boolean hasCycle(Node head) {
        Node a = head,b = head;
        while(b != null && b.next != null) {
            a = a.next;
            b = b.next.next;
            if (a == b)
                return true;
        }
        return false;
    }

    public static void main(String[] args) {
        DoubleLink list = new DoubleLink();
        list.Initiate();
        Scanner scanner = new Scanner(System.in);
        String str = scanner.nextLine();
        String[] strArray = str.split(",");
        for (int i = 0; i < strArray.length; i++) {
            list.Insert(i, strArray[i]);
        }
        System.out.println(list.hasCycle(list.head));
        list.Delete(5);
        for (int i = 0; i < list.size; i++) {
            if(i == list.size - 1)
                System.out.print(list.getNode(i).data);
            else
                System.out.print(list.getNode(i).data + ",");
        }
    }

}
